package com.jc.algorithmes.binarytree;

/**
 * 二叉树的后序遍历：
 * 1.先遍历左右节点，再遍历第根节点，依次类推
 * 2.采用Morris实现
 */

public class MirrorsOrderDemoV2 {

    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7,null,null);
        TreeNode node6 = new TreeNode(6,null,null);
        TreeNode node5 = new TreeNode(5,node6,node7);
        TreeNode node4 = new TreeNode(4,null,null);
        TreeNode node3 = new TreeNode(3,null,null);
        TreeNode node2 = new TreeNode(2,node4,node5);
        TreeNode node1 = new TreeNode(1,node2,node3);

        mirrorsPostOrder(node1);

    }

    public static void mirrorsPostOrder(TreeNode cur){
        if (cur == null){
            return;
        }
        TreeNode root = cur;
        TreeNode mostRight = null;
        while (cur != null){
            mostRight = cur.left;
            if (mostRight != null){
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }

                if (mostRight.right == null){   //建立线索指针
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else { //mostRight.right = cur 删除线索指针
                    mostRight.right = null;
                    printNode(cur.left);
                }
            }
            cur = cur.right;
        }
        printNode(root);
    }


    public static void printNode(TreeNode head){
        TreeNode tail = reverse(head);
        while (tail != null){
            System.out.println(tail.val);
            tail = tail.right;
        }
        reverse(tail);
    }

    //反转
    private static TreeNode reverse(TreeNode head) {
        TreeNode prev = null,curr,next;
        curr = head;
        while (curr != null){
            next = curr.right;
            curr.right = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

}
